package com.zj.base;

import java.util.Arrays;

/**
 * @author zhangbo
 * @program: algorithm
 * @description: $
 * @date 2022-08-22 15:51:33
 */
public class MergeSort03 {


    /**
     * 本质是两数组合并的逻辑，好好记下
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    public void marge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        //左指针
        int i = l;
        //右指针
        int j = mid + 1;
        int k = 0;

        //必须等于
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= r) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[l + m] = temp[m];
        }
    }


    public void sort(int[] arr, int left, int right) {
        int mid = (right - left) / 2 + left;
        if (left < right) {
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            marge(arr, left, mid, right);
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 3, 6, 8, 1, 7, 9, 4, 2, 2, 23, 3, 23, 23, 4, 31, 5, 76, 8, 89};
        MergeSort03 m = new MergeSort03();
        m.sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}
